#include"bitset.h"
struct BKDRHash
{
	size_t operator()(const string& key)
	{
		// BKDR
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

struct APHash
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			char ch = key[i];
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& key)
	{
		size_t hash = 5381;
		for (auto ch : key)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};




template <size_t M, class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
	class BloomFilter
{
public:
	void set(const string& key)
	{
		size_t hash1 = (HashFunc1()(key)) % M;
		size_t hash2 = (HashFunc2()(key)) % M;
		size_t hash3 = (HashFunc3()(key)) % M;

		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
	}

	bool test(const string& key)
	{
		size_t hash1 = (HashFunc1()(key)) % M;
		if (_bs.test(hash1) == false) return false;

		size_t hash2 = (HashFunc2()(key)) % M;
		if (_bs.test(hash2) == false) return false;
		
		size_t hash3 = (HashFunc3()(key)) % M;
		if (_bs.test(hash3) == false) return false;
		
		//存在误判的概率
		return true;
	}
private:
	N::bit_set <M> _bs;
};


